//Copyright 2012 Trevin Liberty
//GNU GPL v3
//Author: Trevin Liberty
//
//An Implementation of the AStar algorithm.

#ifndef A_STAR_H
#define A_STAR_H

#include <iostream>
#include <allegro5\allegro.h>
#include <allegro5\allegro_primitives.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <list>
#include <vector>

using std::cout;
using std::endl;

#include "../../Structs.h"
#include "../../Point.h"
#include "AStarStructs.h"

//SEE: class NODE. Below AStar.
class Node;

//SEE: Top of file
class AStar {
private:
	Map *map;

	Thread_Queue_In *queueIn;
	Thread_Queue_Out *queueOut;

	float h(Node *currentNode, Node *goalNode);
	float g(Node* currentNode, Node* neighborNode);
	list<Node*>* getNeighbors(const Node *node);
	void deleteVector(vector<Node*>* vector);
	void deleteList(list<Node*>* lis);

public:
	//	PARAMS:
	//Map* map: SEE: Structs.h->struct Map{...}
	AStar(Map* map);

	//Returns a path, from start to goal, created by AStar.
	//	PARAMS:
	//Point<int> start: The point at which AStar begins to search for a path.
	//Point<int> goal: The end point at which AStar finishes its search.
	//ALLEGRO_THREAD *thr: The thread that is performing this search. Used to stop the
	//	search if the thread is told to stop. SEE: PathingThread.h
	list<Point<int>>* getPath(Point<int> start, Point<int> goal, ALLEGRO_THREAD *thr);

	//Returns true if QueueIn is empty.
	//	else false
	bool isEmptyQueueIn();

	//Returns true if QueueOut is empty.
	//	else false
	bool isEmptyQueueOut();

	//Returns the front entry in queueIn. Used by pathing thread to start searching for new paths.
	//	Returns NULL if queueIn is empty.
	//SEE: PathingThread.h
	PathingQueueEntry* queueInGet();

	//Used to push a pathing request into queueIN. Pathing threads use this entry to create new paths.
	//	PARAMS:
	//PathingQueueEntry* entry: An entry that will be used to create a new path. SEE: AStarStructs.h
	void addEntry(PathingQueueEntry* entry);

	//Returns a completedPath that was created for Entity.
	//	Returns NULL if queueOut is empty.
	//SEE: PathingThread.h
	//	PARAMS:
	//Entity* e: The Entity that is searching for it completed path.
	CompletedPath* queueOutGet(Entity* e);

	//Removes all requests or completed paths for Entity* e.
	//	PARAMS:
	//Entity* e: The Entity that needs its paths removed.
	void removeEntityPaths(Entity* e);

	//Used to add a newly created path to queueOut. Used by pathing threads.
	//SEE: PathingThreads.h
	//	PARAMS:
	//CompletedPath* path: The path that has been created successfully by AStar.
	//	SEE: AStarStructs.h
	void addCompletedPath(CompletedPath* path);

	~AStar();
};


//Class for representing places/nodes of a map. Used by AStar.
//No use outside of AStar.
//TODO: Move to AStar.cpp?
class Node {
	public:
		Point<int> pos;

		float g;
		float f;

		Node *parent;

		bool isOccupied;

		Node() : g(0), f(0), parent(NULL), isOccupied(false) {pos.x = 0; pos.y = 0;}
		Node(Point<int> p) : g(0), f(0), parent(NULL), isOccupied(false) {pos = p;}

		float getDistance(Node &node);

		bool isGoal(Node &goalNode);

		const bool operator ==(const Node& n) const {
			return this->pos.x == n.pos.x && this->pos.y == n.pos.y;
		}
		
		const bool operator <(const Node& n) const {
			return this->f < n.f;
		}

		const bool operator >(const Node& n) const {
			return this->f > n.f;
		}

		const bool operator <=(const Node& n) const {
			return this->f <= n.f;
		}

		const bool operator >=(const Node& n) const {
			return this->f >= n.f;
		}
};
#endif
